package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class M7 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new LinkedList<>();
        int middle=0;
        int count0=0;
        for (; middle < nums.length; middle++) {
            if (nums[middle]>0) {
                break;
            }
            if (nums[middle]==0) {
                count0++;
            }
        }
        middle-=count0;
        if (count0>=3) {
            LinkedList<Integer> list=new LinkedList<>();
            list.add(0);
            list.add(0);
            list.add(0);
            res.add(list);
        }
        int[] le=new int[middle];
        int[] ri=new int[nums.length-middle];
        for (int i = 0; i < le.length; i++) {
            le[i]=nums[i];
        }
        for (int i = 0; i < ri.length; i++) {
            ri[i]=nums[i+middle];
        }
        HashSet<Integer> hashSet=new HashSet<>();
        // 一个负数找两个正数
        for (int i = 0; i < le.length; i++) {
            if (hashSet.contains(le[i])) {
                continue;
            }
            hashSet.add(le[i]);
            int[] find_res=twoSum(ri, -le[i]);
            if (find_res!=null) {
                LinkedList<Integer> list=new LinkedList<>();
                list.add(le[i]);
                list.add(find_res[0]);
                list.add(find_res[1]);
                res.add(list);
            }
        }
        for (int i = 0; i < ri.length; i++) {
            if (hashSet.contains(ri[i])) {
                continue;
            }
            hashSet.add(ri[i]);
            int[] find_res=twoSum(le, -ri[i]);
            if (find_res!=null) {
                LinkedList<Integer> list=new LinkedList<>();
                list.add(ri[i]);
                list.add(find_res[0]);
                list.add(find_res[1]);
                res.add(list);
            }
        }
        return res;
    }
    public LinkedList<int[]> twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> data=new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (data.containsKey(numbers[i])) {
                return new int[]{numbers[i],target-numbers[i]};
            }
            data.put(target-numbers[i], i);
        }
        return null;
    }
}
